1. Field of the Invention
This invention relates to image processing apparatuses, methods, storage media, and programs. More particularly, the present invention relates to an information processing apparatus, a method, a storage medium, and a program which are capable of promptly detecting a motion vector.
2. Description of the Related Art
FIG. 1 shows an example of the configuration of a known motion detector 1 of an image processing apparatus that compresses a moving picture by utilizing a motion vector indicating the motion of the image (e.g., refer to Japanese Patent Nos. 3277417 and 3271387 and Japanese Examined Patent Application Publication No. 5-62876).
A frame memory 11 stores one-frame image information of an image signal input via an input terminal Tin, and also outputs stored image information to a frame memory 12 and a motion-vector detector 13 when storing the next frame image information that is input.
The frame memory 12 stores one-frame image information input from the frame memory 11, and outputs stored image information to the motion-vector detector 13 when storing the next frame image information that is input from the frame memory 11.
The motion-vector detector 13 uses the one-frame image information input from the frame memory 11 as the image information of a current frame Fc and uses one-frame image information (i.e., the image information of a frame that is one-frame earlier than the frame input from the frame memory 11) input from the frame memory 12 as the image information of a reference frame Fr to thereby detect a motion vector by block matching. The motion-vector detector 13 outputs the detected motion vector via an output terminal Tout.
A block matching algorithm will now be described with reference to FIG. 2. For example, a base block Bb is provided on the current frame Fc and has L pixels×L pixels with a pixel (a target pixel) P(i, j) being the center. The target pixel is observed for detection of a motion vector. Further, a search area SR is provided on the reference frame Fr so as to correspond to the target pixel P(i, j), and reference blocks Brn (n=1, 2, . . . m), which have L pixels×L pixels, are provided within the search area SR.
The sum of absolute differences between individual pixels of the base block Bb and individual pixels of the reference block Brn is calculated for each of the reference blocks Br1 to Brm (the number of reference blocks Brn within the search area SR is assumed to be m) that are provided by movement of the reference block Brn pixel by pixel in the horizontal or vertical direction throughout the search area SR.
A reference block Br from which the thus-calculated sum of absolute differences between the pixels of the base block Bb and the pixels of the reference block Brn becomes a minimum is determined as a reference block Br that is the closest (the most similar) to the base block Bb. Then, a vector that has a starting point at a pixel P′ (i, j) on the reference frame Fr which corresponds to the target pixel P (i, j) on the current frame Fc and that has an end point at the center pixel Pn (i, j) of the reference block Brn that is detected as being the closest to the base block Bb is output as a motion vector V (Vx, Vy) of the target pixel P(i, j).
Next, a motion detection process of the motion detector 1 shown in FIG. 1 will be described with reference to the flow chart of FIG. 3.
In step S1, the motion-vector detector 13 sets a search area SR according to the pixel position of the target pixel p (i, j) on the current frame Fc input from the frame memory 11.
In step S2, the motion-vector detector 13 initializes a variable min for setting the minimum value of the sum of absolute differences between the pixel values of pixels of the base block Bb and the pixel values of pixels of the reference block Brn. Specifically, the variable min is set to a value that is obtained by multiplying the number of gray levels of a pixel by the number of pixels constituting the base block Bb. For example, when one pixel has 8-bit data and the base block Bb is constituted by 3 pixels×3 pixels, the number of gray levels of one pixel is 256 gray levels (256 colors) (=2 to the eighth power) and the number of pixels is 9, so that the variable min is initialized to 2304 (=256×9).
In step S3, the motion-vector detector 13 initializes a counter variable n, which is used for counting of the number of generated reference blocks Br, to “1”.
In step S4, the motion-vector detector 13 initializes a variable sum, to which the sum of absolute differences between the pixels of the base block Bb and the reference block Brn is assigned, to “0”.
In step S5, the motion-vector detector 13 calculates the sum of absolute differences between the pixels of the base block Bb and the reference block Brn. That is, the motion-vector detector 13 calculates the sum of absolute differences between the pixels of the base block Bb and the reference block Brn by performing an operation shown in expression (1). In expression (1), P_Bb (i, j) represents each pixel of the base block Bb and P_Brn (i, j) represents each pixel of the reference block Brn.
                    sum        =                              ∑                          i              =              1                        L                    ⁢                                          ⁢                                    ∑                              j                =                1                            L                        ⁢                                                  ⁢                                                                          (                                      P_Bb                    ⁢                                          (                                              i                        ,                        j                                            )                                                        )                                -                                  (                                      P_Brn                    ⁢                                          (                                              i                        ,                        j                                            )                                                        )                                                                                                      (        1        )            
In step S6, the motion-vector detector 13 determines whether the variable min is greater than the variable sum. When it is determined that the variable min is greater, the process proceeds to step S7, in which the variable min is replaced with the variable sum and the value of the counter variable n at this point is registered as a motion vector number. That is, when the just-obtained variable sum indicating the sum of absolute differences, is smaller than the variable min indicating the minimum value, it is possible to estimate that the reference block Br that is currently calculated is the most similar to the base block Bb than any other reference blocks Br that have been calculated so far. Thus, that reference block Br is regarded as a candidate for determining the motion vector and the counter variable n at this point is registered as a motion vector number.
In step S6, when it is determined that the variable min is not greater than the variable sum, the process skips step S7.
In step S8, the motion-vector detector 13 determines whether the counter variable n is equal to the total number m of the reference blocks Br within the search area SR, i.e., whether the current reference block Br is the reference block Brm. For example, when it is determined that the counter variable n is not equal to the total number m, in step S9, the counter variable n is incremented by “1” and the process returns to step S4.
In step S8, when it is determined that the counter variable n is equal to the total number m of the reference blocks Br within the search area SR, i.e., when it is determined that the current reference block Br is the reference block Brm, in step S10, the motion-vector detector 13 outputs a motion vector according to the registered motion vector number. That is, steps S4 to S9 are repeated so that the counter variable n corresponding to the reference block Brn from which the sum of absolute differences becomes a minimum is registered as a motion vector number. Thus, the motion-vector detector 13 determines, as a motion vector V(Vx, Vy) of the target pixel P(i, j), a vector that has a starting point at a pixel P′ (i, j) on the reference frame Fr which corresponds to the target pixel P (i, j) on the current frame Fc and that has an end point at the center pixel Pn (i, j) of the reference block Brn which corresponds to the motion vector number and outputs the determined vector.
The above-described block matching, however, has a problem in that a motion vector cannot be promptly detected because of an enormous amount of computation required for expression (1).